package LeetCode刷题;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-29 18:40
 * @description: Functions of this class is
 * 官方解法(性能法）：
 * // 4. 追求程序的极致性能
 * // s 由英文字母、数字、符号和空格组成
 * public int lengthOfLongestSubstring(String s) {
 *     int n = s.length();
 *     if (n <= 1) return n;
 *     int maxLen = 1;
 *
 *     int left = 0, right = 0;
 *     int[] window = new int[128];
 *     while (right < n) {
 *         char rightChar = s.charAt(right);
 *         int rightCharIndex = window[rightChar];
 *         left = Math.max(left, rightCharIndex);
 *         maxLen = Math.max(maxLen, right - left + 1);
 *         window[rightChar] = right + 1;
 *         right++;
 *     }
 *
 *     return maxLen;
 * }
 **/
public class No最长连续序列不能用排序 {
    public static void main(String args[]) {
        System.out.println(longestConsecutive(new int[]{100,4,200,1,3,2}));//3
    }

    public static int longestConsecutive(int[] nums) {
        if(nums.length==0||nums.length==1){
            return nums.length;
        }
       HashSet<Integer>set=new HashSet<>();
       for(int num:nums){
           set.add(num);//利用Set的特性去除重
       }
       int ans=0;//用以记录当前答案
        /**
         * 以下算法，关键就是从这些数字中找到不在之前路径中的的起点，然后看能否以此为起点来找到一条更长的路径来作为答案
         */
       for(int num:set){
           if(!set.contains(num-1)){//如果不存在当前数字的上一位，
               int startNum=num;//说明该数字可以作为路径的起点
               int len=1;//路径长度的初始值为1
               while(set.contains(startNum+1)){//找寻以此起点开始的路径最长有多少
                   startNum++;
                   len++;
               }
               ans=Math.max(ans,len);
           }
       }
        return ans;
    }
}